1. Field of the Invention
The present invention relates to a first-in first-out (FIFO) data pipeline having a plurality of stages, and more particularly, to a pipeline stage in the FIFO that makes a data element received at the pipeline stage available to the next stage in the FIFO before the pipeline stage has latched the data element.
2. Description of the Related Art
FIFO pipelines are widely used in the computer, telecommunication, and related fields for the handling of data elements. A FIFO pipeline includes a plurality of N stages. Data elements enter at one end of the pipeline, and in a succession of steps, progress from one stage to the next. Eventually, the data elements exit the pipeline at the last or Nth stage, in the same order in which the data elements entered the FIFO (i.e., first-in first-out). FIFOs may be either synchronous or asynchronous. In a synchronous FIFO, the stages operate within the rhythm imposed from an outside source, such as a clock. Each task that is performed at a particular stage must be completed within the clock period. With asynchronous FIFOs, each stage operates at its own pace.
Referring to FIG. 1, a block diagram of a FIFO is shown. The FIFO 10 includes a plurality of stages 12a through 12n. Each stage 12 includes a data latch block 14 and a corresponding control block 16. It is useful to note that throughout the following discussion, the term "current" stage is defined as a particular stage 12, the term "previous" stage is defined as the stage just prior to the current stage, and the "next" stage is defined as the stage immediately after the current stage. For example, if stage 12b is the current stage, then stage 12c is the next stage and stage 12a is the previous stage.
Each data latch block 14 is designed to operate in two states, either transparent or opaque. In the transparent state, the data element appearing at the output Dout of the latch block 14 is identical to the data element appearing at the input Din of latch block 14. If the data element at Din changes during the transparent state, the data element at Dout changes accordingly after a relatively minor propagation delay through the latch block 14. On the other hand, in the opaque state, the data element at output Dout of the latch block 14 remains static, regardless of whether the data element at the input Din of the latch block 14 changes. Accordingly, the data element in the latch block 14 is said to be held or latched in the opaque state.
The control block 16 of each stage 12 is responsible for managing data transfer in the FIFO 10. This management responsibility can be viewed as two interrelated tasks: control between neighboring control circuits 16 of adjacent stages 12; and control between the control block 16 and the corresponding data latch block 14 of each stage 12.
The control between the neighboring control circuits 16 of adjacent stages 12 is implemented using signals Request input (Ri), Request output (Ro), Acknowledge input (Ai), and Acknowledge output (Ao). The relationship between signals Ri, Ro, Ai, and Ao is best described using an example. Consider stage 12b as the current stage. On the input side of the current stage 12b, control block 16b receives signal Ri from control block 16a of the previous stage 12a, and signal Ai is generated by the control block 16b of the current stage 12b and provided to the control block 16a of the previous stage 12a. On the output side of the current stage 12b, the control block 16b generates signal Ro and provides it to the control block 16c of the next stage 12c, and signal Ao is received at the control block 16b from control block 16c of the next stage 12c. Signal Ro generated by the control block 16b of the current stage 12b is signal Ri received by the control block 16c of the next stage 12c, and signal Ai generated by the control block 16b of the current stage 12b is signal Ao received by the control block 16a of the previous stage 12a. The above defined relationship is similar for each stage 12 in the FIFO 10.
The significance of signals Ri, Ro, Ai and Ao is described below.
Ri--Indicates to the current stage that the data element appearing at input Din of the corresponding latch is valid and is available for latching; PA1 Ro--Informs the next stage that the data element appearing on the output Dout of the current stage is valid and is available to the next stage for latching; PA1 Ai--Indicates that the current stage has latched the data element appearing on its input Din; and PA1 Ao--Informs the current stage that the next stage has latched the data element appearing on output Dout of the current stage and allows the current stage to announce new valid data Dout when it becomes available.
The control between the control block 16 and its corresponding latch block 14 of each stage 12 is implemented using two signals, L and G. When the control block 16 sets signal L, it directs the latch block 14 to become opaque. In time, the latch block 14 sets signal G to inform the control block 16 that the latch block 14 has in fact become opaque. With two signals (L and G), the latch block 14 can be in one of four possible states at any given point in time. The four states are described in TABLE I below:
TABLE I ______________________________________ L G State ______________________________________ 0 0 Transparent state 1 0 Latching state 1 1 Opaque state 0 1 Unlatching state ______________________________________
In the Transparent state, the control block 16 is directing the latch block 14 to be transparent (L=0) and the actual state of the latch is transparent. In the Latching state , the control block 16 instructs the latch block 14 to become opaque, but the latch block 14 has not yet become opaque. In the Opaque state, the data element at Din at the input of the latch block 14 is safely latched. In the Unlatching state, the latch block 14 is unlatching and the data element at its output Dout is unreliable.
In the paper entitled "FIFO Controls for Four Stage Storage Elements" Sutherland, Sproull and Associates, publication number 4179, by Robert F. Sproull, Sep. 22, 1985, several control circuits for a FIFO are disclosed. In particular, FIGS. 5A-5C in the paper illustrate recommended control circuits for a transition signaling FIFO having latches that are normally transparent. With these circuits, signal "R" (analogous to signal Ro) and the signal "a" (analogous to signal Ai) are in fact the same signal and they are not generated until the latch is opaque. FIGS. 4A-4C in the paper illustrate recommended control circuits for a transition signaling FIFO having latches that are normally opaque. The signal "R" is generated only after (1) the signal "r" (analogous to signal Ri) is received from the previous stage, (2) the signal "A" (analogous to signal Ao) is received from the next stage, and (3) after the unlatching of the latch and data propagation time (t.sub.1) through the latch. In other words, signal "R" is not asserted until the normally opaque latch first transitions to the transparent state and propagates the data through the latch.
A problem with the control circuits of the prior art is that they significantly impede the rate at which data elements can progress from a current stage to the next stage. In the two prior art circuits mentioned above, either a latching or an unlatching action of the latch must take place before the current stage can forward propagate the data element to the next stage. This problem adversely affects the performance of a FIFO in two critical performance measures. The latency period, which is defined as the period of time it takes for a data element to enter and then exit the FIFO, is significantly increased. The data throughput rate is also considerably slowed at each stage 12.